package pers.zc.activiti.service.impl;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Annotion:
 * @ClassName: TestCyle
 * @Author: Lin Fuyuan
 * @Date: 2019/9/27  14:48
 * @Version: 1.0
 */
public class TestCycle {
    private int n;//节点个数
    private int[] visited;//节点状态,值为0的是未访问的
    private int[][] e;//有向图的邻接矩阵,
    private ArrayList<Integer> trace = new ArrayList<Integer>();//从出发节点到当前节点的轨迹
    private boolean hasCycle = false;//是否有环

    /*初始化数据*/
    public TestCycle(int n, int[][] e) {
        this.n = n;
        visited = new int[n];//新建长度为n的数组
        Arrays.fill(visited, 0);//初始化所有数据为0
        this.e = e;//矩阵数据
    }

    //递归DFS
    public void findCycle(int v) { //v:找一个初始节点
//        System.out.println("v:"+v);
        if (visited[v] == 1) {
            int j;
            if ((j = trace.indexOf(v)) != -1) {
                hasCycle = true;
                System.out.print("Cycle:");
//                while (j < trace.size()) {
//                    System.out.print(trace.get(j) + " ");
//                    j++;
//                }
                System.out.print(trace.toString()+"\n");
                return;
            }
            System.out.println(trace.toString());
            return;
        }
        visited[v] = 1;
        trace.add(v);

        for (int i = 0; i < n; i++) {
            if (e[v][i] == 1) {
                findCycle(i);
            }
        }
        trace.remove(trace.size() - 1);
    }

    public boolean getHasCycle() {
        return hasCycle;
    }

    public static void main(String[] args) {
        int n=7;
        int[][] e={
                {0,1,1,0,0,0,0},
                {0,0,0,1,0,0,0},
                {0,0,0,0,0,1,0},
                {0,0,0,0,1,0,0},
                {0,0,1,0,0,0,0},
                {0,0,0,0,1,0,1},
                {1,0,1,0,0,0,0}};//有向图的邻接矩阵,值大家任意改.
//        int n = 5;
//        int[][] e = {
//                {0, 1, 0, 0, 1},
//                {0, 0, 1, 1, 0},
//                {0, 0, 0, 0, 1},
//                {0, 0, 0, 0, 0},
//                {0, 1, 0, 1, 0}
//        };
        TestCycle tc = new TestCycle(n, e);
        tc.findCycle(0);
        if (!tc.hasCycle) {
            System.out.println("No Cycle.");
        }



    }
}